package cn.lishiyuan.algorithm.strings;

import java.util.HashMap;
import java.util.Map;

/**
 * Rabin-Karp 算法
 */
public class BMMatcher implements Matcher{

    @Override
    public boolean match(CharSequence source, CharSequence word) {
        return find(source,word) != -1;
    }

    @Override
    public int find(CharSequence source, CharSequence word) {
        // codePoints或者chars
        int[] sourceArray = source.chars().toArray();
        int[] wordsArray = word.chars().toArray();

        if (sourceArray.length < wordsArray.length){
            return -1;
        }

        if (wordsArray.length == 0){
            return -1;
        }

        int index = -1;

        Map<Integer, Integer> badWordsTable = buildBadWordsTable(wordsArray);

        Map<Integer,Integer> suffix = new HashMap<>();
        Map<Integer,Boolean> prefix = new HashMap<>();
        buildGoodSuffixTable(wordsArray,suffix,prefix);

        int i = 0;

        for (; i < sourceArray.length - wordsArray.length + 1; ){
            int j = wordsArray.length - 1;
            for (; j >=0 ;){
                // 坏字符规则，从后向前匹配
                if(wordsArray[j] != sourceArray[i+j]){
                    break;
                }
                j--;
            }

            // j 是坏字符位置
            if (j == -1){
                // 找到了
                index = i;
                break;
            }

            // 从坏字符表中查找
            int badWord = sourceArray[i+j];
            Integer badWordIndex = badWordsTable.getOrDefault(badWord, -1);

            // 坏字符规则移动的步长
            int x = j - badWordIndex;
            // 好后缀规则移动的步长
            int y = 0;

            // 好后缀最少一个字符
            if(j < (wordsArray.length-1)){
                // 处理好后缀的情况
                // 好后缀的长度
                int len = wordsArray.length - 1 - j;
                Integer suffixIndex = suffix.getOrDefault(len, -1);
                if(suffixIndex != -1){
                    // 如果存在前一个好后缀，则需要对齐
                    /**
                     * 123223424
                     * 323423
                     * 此时23好后缀的前一个位置是1，此时坏字符位置是3，需要滑动3个位置才能对齐
                     */
                    y = (j - suffixIndex + 1);
                }else {
                    // 前缀对齐
                    // j是坏字符位置，j + 1就是好后缀长度，此时好后缀必然不存在，所以r从j+2开始
                    int r = j + 2;
                    for (; r < wordsArray.length; r++) {
                        // 获取好后缀的后缀是否有公共前后缀，串长度= length - index
                        if (prefix.getOrDefault(wordsArray.length - r,false)) {
                            y= r;
                            break;
                        }
                    }
                }
            }

            i += Math.max(x,y);
        }
        return index;
    }

    private Map<Integer,Integer> buildBadWordsTable(int[] wordsArray){
        Map<Integer, Integer> badwords = new HashMap<>();
        for (int i = 0; i < wordsArray.length; i++) {
            // 如果有相同的字符，使用后一个index替换掉
            badwords.put(wordsArray[i], i);
        }
        return badwords;
    }

    private void buildGoodSuffixTable(int[] wordsArray,Map<Integer,Integer> suffix,Map<Integer,Boolean> prefix){
        // 构建
        for (int i = 0; i < wordsArray.length - 1; i++) {
            int j = i;
            int len = 0;
            // i->0 与 末尾 -> j 进行逆序的对比
            // 每次都会从最后一个字符开始匹配，这使得始终存靠近末尾的子串
            // 相当于每次从j到0寻找匹配模式串末尾到len长度的子串
            /**
             * [1][2][3][4][5][5]
             *   ←j↑         ←(↑ wordsArray.length - 1 -len )
             */
            while (j >= 0 && wordsArray[j] == wordsArray[wordsArray.length - 1 -len]){
                suffix.put(len,j);
                j--;
                len++;
            }

            // 如果匹配首位则说明可以对齐公共前后缀
            if(j == -1){
                prefix.put(len,true);
            }
        }
    }
}
